We concern the problem of modifying the edge lengths of a tree in minimumtotal cost so that the prespecified $p$ vertices become the $p$-maxian withrespect to the new edge lengths. This problem is called the inverse $p$-maxianproblem on trees. \textbf{Gassner} proposed efficient combinatorial alogrithmto solve the the inverse 1-maxian problem on trees in 2008. For the problemwith $p \geq 2$, we claim that the problem can be reduced to finitely manyinverse $2$-maxian problem. We then develop algorithms to solve the inverse$2$-maxian problem for various objective functions. The problem under$l_1$-norm can be formulated as a linear program and thus can be solved inpolynomial time. Particularly, if the underlying tree is a star, then theproblem can be solved in linear time. We also devised $O(n\log n)$ algorithmsto solve the problems under Chebyshev norm and bottleneck Hamming distance,where $n$ is the number of vertices of the tree. Finally, the problem underweighted sum Hamming distance is $NP$-hard.
展开▼
机译：我们关注以最小的总成本修改树的边长的问题，以便相对于新边长，预先指定的$ p $顶点成为$ p $ -maxian。这个问题称为树上的逆$ p $ -maxian问题。 \ textbf {Gassner}在2008年提出了有效的组合算法来解决树上的1-maxian逆问题。对于$ p \ geq 2 $的问题，我们认为该问题可以简化为有限的$ 2 \ maxian逆问题。然后，我们开发算法来解决各种目标函数的反2-maxian问题。 $ l_1 $ -norm下的问题可以表示为线性程序，因此可以解决多项式时间。特别地，如果基础树是星形，则可以在线性时间内解决问题。我们还设计了$ O（n \ log n）$算法来解决Chebyshev范数和瓶颈汉明距离下的问题，其中$ n $是树的顶点数。最后，问题的加权总和汉明距离是$ NP $ -hard。
展开▼
